package org.hot100_0.leetcode105;

import org.leetcode.TreeNode;

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode res = makeTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
        return res;
    }

    private TreeNode makeTree(int[] preorder, int[] inorder, int preStartIndex, int preEndIndex, int inStartIndex, int inEndIndex) {

        if (preStartIndex > preEndIndex) {
            return null;
        }

        int rootVal = preorder[preStartIndex];

        TreeNode node = new TreeNode(rootVal);

        int rootIndex = -1;
        for (int i = inStartIndex; i <= inEndIndex; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
            }
        }


        int inLeftStartIndex = inStartIndex;
        int inLeftEndIndex = rootIndex-1;

        int leftTreeLength = inLeftEndIndex - inLeftStartIndex;

        int preLeftStartIndex = preStartIndex+1;
        int preLeftEndIndex = preLeftStartIndex+leftTreeLength;

        int inRightStartIndex = rootIndex+1;
        int inRightEndIndex = inEndIndex;

        int preRightStartIndex = preLeftEndIndex+1;
        int preRightEndIndex = preEndIndex;


        node.left = makeTree(preorder,inorder,preLeftStartIndex,preLeftEndIndex,inLeftStartIndex,inLeftEndIndex);

        node.right = makeTree(preorder,inorder,preRightStartIndex,preRightEndIndex,inRightStartIndex,inRightEndIndex);

        return node;
    }


}
